ZigZag Conversion || Roman to Integer || Longest Common Prefix

发表于

ZigZag Conversion

Question

The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

1
2
3
4
5
6
> P   A   H   N
>
> A P L S I I G
>
> Y   I   R`
>

>

And then read line by line: “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);
convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”.

Analysis

利用数组的下标排列后可以发现每行中脚标的间隔规律，其中第一行和最后一行的间隔为interval=2*numrows-2，中间行的规律与每行的行号有关系，间隔大小是interval-2i与2i的交替重复，所以可以取当前行号i为baseindex,对baseindex交替与两个间隔加和并判断是否超过了最大脚标。行号循环时由于可能出现numrows>size的情况出现，所以需要对两个条件进行判断

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class Solution {
    public String convert(String s, int numRows) {
        int size=s.length();
        if(size==0||numRows==1||size==1)
            return s;
        StringBuilder result=new StringBuilder();
        int interval=numRows*2-2;
        for(int i=0;i<size;i+=interval){
           result.append(s.charAt(i));
        }
        for(int j=1;j<numRows-1&&j<size;j++){
            int inteven=interval-2*j;
            int intodd=2*j;
            result.append(s.charAt(j));
            int index=j;
            while(index<size){
                index+=inteven;
                if(index<size){
                    result.append(s.charAt(index));
                }else{
                    break;
                }
                index+=intodd;
                if(index<size){
                    result.append(s.charAt(index));
                }
            }
        }
        for(int m=numRows-1;m<size;m+=interval){
            result.append(s.charAt(m));
        }
        String finalres=result.toString();
        return finalres;
    }
}

Roman to Integer

Question

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Analysis

罗马数字规则

I V X L C D M
1 5 10 50 100 500 1000
  • 在较大的罗马数字的右边记上较小的罗马数字，表示大数字加小数字。
  • 在较大的罗马数字的左边记上较小的罗马数字，表示大数字减小数字。
  • 左减的数字有限制，仅限于I、X、C。比如45不可以写成VL，只能是XLV，但是，左减时不可跨越一个位值。比如，99不可以用IC（100-1）表示，而是用XCIX（[100-10]+[10-1]）表示。（等同于阿拉伯数字每位数字分别表示。）
  • 左减数字必须为一位，比如8写成VIII，而非IIX。
  • 右加数字不可连续超过三位，比如14写成XIV，而非XIIII。（见下方“数码限制”一项。）

思路

一开始打算设置subflag和addflag控制加减，发现好蠢- -，可以每次都默认是加，当发现右侧的数字大于左侧的时候则将右侧的加上，减去2倍的左侧数字。而最好是从第二位开始，这样每次都与前面previous比较也不用考虑数组下标超出的问题。在用case的时候注意return就已经跳出了switch，不需要再加入break。

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class Solution {
    public int romanToInt(String s) {
        int size=s.length();
        int result=renum(s.charAt(0));
        for(int i=1;i<size;i++){
            int current=renum(s.charAt(i));
            int previous=renum(s.charAt(i-1));
            if(current<=previous){
                result+=current;
            }else{
                result-=2*previous-current;
            }
        }
        return result;
    }
    
    public int renum(Character c){
        switch(c){
            case 'I':
                return 1;
            case 'V':
                return 5;
            case 'X':
                return 10;
            case 'C':
                return 100;
            case 'L':
                return 50;
            case 'D':
                return 500;
            case 'M':
                return 1000;
            default:
                return -1;
        }
    }
}

Longest Common Prefix

Question

Write a function to find the longest common prefix string amongst an array of strings.

Analysis

利用strs中的第一个字符串（将其设定为prefix）开始与之后的每个字符串进行比对，记录每次第一个不同的位置j，对原有的prefix进行剪切后再利用剪切后的prefix依次向下比对。需要注意对为空或者长度为1的数组的处理。

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public String longestCommonPrefix(String[] strs) {
        int size=strs.length;
        if(strs==null||size==0){
            return "";
        }
        String prefix=strs[0];
        for(int i=1;i<size;i++){
            int j=0;
            while(j<prefix.length()&&j<strs[i].length()&&prefix.charAt(j)==strs[i].charAt(j)){
                j++;
            }
            if(j==0)
                return "";
            prefix=prefix.substring(0,j);
        }
        return prefix;
    }
}